home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 11 - 1995 / 11.12 Dec 95 / Master.c < prev   
Encoding:
C/C++ Source or Header  |  1995-10-10  |  6.5 KB  |  246 lines  |  [TEXT/ttxt]
  1. /*  October 95 Programmer's challenge solution.
  2.     MindReader - By Xan Gregg, Durham, NC.
  3.     
  4.     I try to minimize the number of guesses without
  5.     adding too much complexity too our the code.  First
  6.     I figure out how many of each color are present
  7.     in the answer by essentially repeatedly guessing
  8.     all of each color.
  9.     
  10.     Then I figure out the correct positions one at a time
  11.     starting at slot 0.  I exchange it with each other
  12.     slot (one at a time) until the correct color is found.
  13.     When there is a change in the numCorrect response from
  14.     checkGuess I can tell which of the two slots caused
  15.     the change by looking at my remembered information or,
  16.     if necessary, by performing a second guess with one of
  17.     the colors in both slots.
  18.     
  19.     The "remembered information" includes keeping track
  20.     of colors that were determined (via the numCorrect
  21.     change) to be wrong before and/or a swap is made. This
  22.     doesn't help out too often, but it doesn't take much
  23.     time to record compared to calling checkGuess.
  24.     
  25.     While the outer loop determines the color of
  26.     each slot "left-to-right" (0 to n-1), I found
  27.     that indexing the inner loop right-to-left
  28.     instead of left-to-right increased the speed
  29.     by 30% - 40%.  I wish I understood why!
  30.     
  31.     Oddly, the checkGuess function spends most of its
  32.     time figuring out the numWrong value, which we
  33.     generally ignore.
  34. */
  35.  
  36. typedef void (*CheckGuessProcPtr)(
  37.         unsigned char  *theGuess,
  38.         unsigned short *numInCorrectPos,
  39.         unsigned short *numInWrongPos);
  40.  
  41.  
  42. void MindReader(
  43.         unsigned char  theAnswer[],
  44.         CheckGuessProcPtr checkGuess,
  45.         unsigned short answerLength,
  46.         unsigned short numColors);
  47.  
  48. #define kMaxLength 16
  49.  
  50. #define Bit(color) (1L << (long) (color))
  51.  
  52.  
  53. void MindReader(unsigned char guess[],
  54.         CheckGuessProcPtr checkGuess,
  55.         unsigned short answerLength,
  56.         unsigned short numColors)
  57. {
  58.     long        prevColorsFound;
  59.     long        colorsFound;
  60.     long        curColor;
  61.     long        i, j;
  62.     long        curCorrect;
  63.     long        numOfColor[kMaxLength + 1];    /* 1-based */
  64.     Boolean        isCorrect[kMaxLength];
  65.     long        possibilities[kMaxLength];    /* bit fields */
  66.     long        colorBit1;
  67.     long        colorBit2;
  68.     char        color1;
  69.     char        color2;
  70.     long        delta;
  71.     unsigned short    newCorrect;
  72.     unsigned short    newWrong;
  73.     
  74.     /* first find the correct set of colors */
  75.     colorsFound = 0;
  76.     curColor = 1;
  77.     while (colorsFound < answerLength)
  78.      {
  79.         for (i = colorsFound; i < answerLength; i++)
  80.             guess[i] = curColor;
  81.         (*checkGuess)(guess, &newCorrect, &newWrong);
  82.         prevColorsFound = colorsFound;
  83.         colorsFound = newCorrect + newWrong;
  84.         numOfColor[curColor] = colorsFound - prevColorsFound;
  85.         curColor++;
  86.      }
  87.     
  88.     /* now work on the order */
  89.     for (i = 0; i < answerLength; i++)
  90.      {
  91.         isCorrect[i] = false;
  92.         possibilities[i] = -1;    /* all colors */
  93.      }
  94.     curCorrect = newCorrect;
  95.     /* step through every slot, starting at 0 */
  96.     for (i = 0; curCorrect < answerLength; i++)
  97.      {
  98.         if (isCorrect[i])
  99.             continue;
  100.         color1 = guess[i];
  101.         colorBit1 = Bit(color1);
  102.         /* try swapping slot i with every other open */
  103.         /* slot, starting with the last one */
  104.         j = answerLength;
  105.         nextSubSlot:
  106.         j--;
  107.         if (guess[i] == guess[j])
  108.             goto nextSubSlot;
  109.         if (isCorrect[j])
  110.             goto nextSubSlot;
  111.         color2 = guess[j];
  112.         colorBit2 = Bit(color2);
  113.         if ((possibilities[i] & colorBit2) == 0)
  114.             goto nextSubSlot;    /* no hope here */
  115.         /* swap slots i & j and check result */
  116.         guess[i] = color2;
  117.         guess[j] = color1;
  118.         (*checkGuess)(guess, &newCorrect, &newWrong);
  119.         delta = newCorrect - curCorrect;
  120.         if (delta >= 0)
  121.         if (delta == 0)
  122.          {    /* either both are incorrect OR */
  123.             /* one is correct and answer[i]==answer[j] */
  124.             guess[i] = color1;
  125.             guess[j] = color2;
  126.             if (numOfColor[color1] == 1)
  127.              {    /* color1 can't be in both places */
  128.                 possibilities[i] &= ~colorBit1;
  129.                 possibilities[j] &= ~colorBit1;
  130.              }
  131.             if (numOfColor[color2] == 1)
  132.              {    /* color2 can't be in both places */
  133.                 possibilities[i] &= ~colorBit2;
  134.                 possibilities[j] &= ~colorBit2;
  135.              }
  136.          }
  137.         else if (delta == 1)
  138.          {    /* both were wrong, now one is correct */
  139.             /* find out which is correct */
  140.             curCorrect = newCorrect;
  141.             if ((possibilities[j] & colorBit1) == 0)
  142.              {    /* i must be color2 */
  143.                 possibilities[j] &= ~colorBit2;
  144.                 numOfColor[color2] -= 1;
  145.                 goto nextSlot;
  146.              }
  147.             else if ((possibilities[i] & colorBit2) == 0)
  148.              {    /* j must be color1 */
  149.                 isCorrect[j] = true;
  150.                 possibilities[i] &= ~colorBit1;
  151.                 numOfColor[color1] -= 1;
  152.                 color1 = color2;
  153.                 colorBit1 = colorBit2;
  154.              }
  155.             else
  156.              {    /* we'll have to make another guess to */
  157.                 /* see which is correct */
  158.                 guess[i] = color1;
  159.                 (*checkGuess)(guess, &newCorrect, &newWrong);
  160.                 if (newCorrect == curCorrect)
  161.                  {    /* j must be color1 */
  162.                     possibilities[i] &=
  163.                                 (~(colorBit1 | colorBit2));
  164.                     isCorrect[j] = true;
  165.                     guess[i] = color2;
  166.                     numOfColor[color1] -= 1;
  167.                     color1 = color2;
  168.                     colorBit1 = colorBit2;
  169.                  }
  170.                 else
  171.                  {    /* i must be color2 */
  172.                     possibilities[j] &=
  173.                                 (~(colorBit1 | colorBit2));
  174.                     guess[i] = color2;
  175.                     numOfColor[color2] -= 1;
  176.                     goto nextSlot;
  177.                  }
  178.              }
  179.          }
  180.         else    /* delta == 2 */
  181.          {    /* both were wrong, now both correct */
  182.             isCorrect[j] = true;
  183.             numOfColor[color1] -= 1;
  184.             numOfColor[color2] -= 1;
  185.             curCorrect = newCorrect;
  186.             goto nextSlot;
  187.          }
  188.         else    /* delta < 0 */
  189.         if (delta == -1)
  190.          {    /* one was correct before swap, now neither is */
  191.             guess[i] = color1;
  192.             guess[j] = color2;
  193.             if ((possibilities[i] & colorBit1) == 0)
  194.              {    /* color2 in slot j was correct */
  195.                 isCorrect[j] = true;
  196.                 numOfColor[color2] -= 1;
  197.                 possibilities[i] &= ~colorBit2;
  198.              }
  199.             else if ((possibilities[j] & colorBit2) == 0)
  200.              {    /* color1 in slot i was correct */
  201.                 possibilities[j] &= ~colorBit1;
  202.                 numOfColor[color1] -= 1;
  203.                 goto nextSlot;
  204.              }
  205.             else
  206.              {    /* we'll have to make another guess to */
  207.                 /* see which was correct */
  208.                 guess[j] = color1;
  209.                 (*checkGuess)(guess, &newCorrect, &newWrong);
  210.                 if (newCorrect == curCorrect)
  211.                  {    /* color1 in slot i was correct */
  212.                     possibilities[j] &=
  213.                                 (~(colorBit1 | colorBit2));
  214.                     guess[j] = color2;
  215.                     numOfColor[color1] -= 1;
  216.                     goto nextSlot;
  217.                  }
  218.                 else
  219.                  {    /* color2 in slot j was correct */
  220.                     possibilities[i] &=
  221.                                 (~(colorBit1 | colorBit2));
  222.                     guess[j] = color2;
  223.                     isCorrect[j] = true;
  224.                     numOfColor[color2] -= 1;
  225.                  }
  226.              }
  227.          }
  228.         else    /* delta == -2 */
  229.          {    /* both were already correct */
  230.             guess[i] = color1;
  231.             guess[j] = color2;
  232.             isCorrect[j] = true;
  233.             numOfColor[color1] -= 1;
  234.             numOfColor[color2] -= 1;
  235.             goto nextSlot;
  236.          }
  237.         goto nextSubSlot;
  238.         nextSlot: ;
  239.      }
  240.     done: ;
  241. }
  242.  
  243.  
  244.  
  245.  
  246.